We consider several combinatorial optimization problems which combine theclassic shop scheduling problems, namely open shop scheduling or job shopscheduling, and the shortest path problem. The objective of the obtainedproblem is to select a subset of jobs that forms a feasible solution of theshortest path problem, and to execute the selected jobs on the open (or job)shop machines to minimize the makespan. We show that these problems are NP-hardeven if the number of machines is two, and cannot be approximated within afactor less than 2 if the number of machines is an input unless P=NP. Wepresent several approximation algorithms for these combination problems.
展开▼
